package de.dhbw.minf12.mas;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * Permutation von Integer Werten
 * @author flo
 *
 */
public class Permutation {
	
	private List<Integer> data;

	public Permutation(List<Integer> pData) {
		super();
		this.data = pData;
	}
	
	/**
	 * Neue Permutation mit 0 bis (pElementCount - 1)
	 * @param pElementCount
	 */
	public Permutation(int pElementCount){
		data = new ArrayList<Integer>(pElementCount);
		
		for(int i = 0; i < pElementCount; i++){
			data.add(i);
		}
	}
	
	public void sortRandomly(){
		Random rand = new Random();
		List<Integer> newList = new LinkedList<Integer>();
		
		while(newList.size() < data.size()){
			int randPosition = rand.nextInt(data.size());
			Integer tmpValue = data.get(randPosition);
			if(!newList.contains(tmpValue)){
				newList.add(tmpValue);
			}
		}
		data = newList;
	}

	public List<Integer> getData() {
		return data;
	}
	
	public int get(int pIndex){
		return this.data.get(pIndex);
	}
	
	public int size(){
		return data.size();
	}
	
	/**
	 * Überprüft, ob die Permutationen gleich sind
	 * @param other
	 * @return
	 */
	public boolean isSame(Permutation other){
		if(other.size() != data.size()){
			return false;
		}
		
		for (int i = 0 ; i < data.size() ; i++) {
			if(data.get(i) != other.get(i)){
				return false;
			}
		}
		
		return true;
	}
	
	/**
	 * Berechnet alle Nachbarn, die durch einfaches vertauschen
	 * gebildet werden k�nnen und gibt eine zuf�llige Auswahl davon
	 * zur�ck.
	 * @param number Anzahl der zur�ckgegebenen Permutaionen. Wenn
	 *   number aber gr��er als die Maximale Anzahl an Permutationen
	 *   ist [(n*(n+1))/2] wird nur die maximale Anzahl zur�ckgegeben. 
	 * @return
	 */
	public List<Permutation> getNeighbors(int number){
		List<Permutation> tmpList = new LinkedList<Permutation>();
		/*Integer tmpforSwap;
		
		// Generate all possible swaps
		int firstPosition = 0;
		int secondPosition = 1;
		while (true) {
			List<Integer> listPerm = new LinkedList<Integer>(data);
			
			if(secondPosition >= listPerm.size()) {
				++firstPosition;
				secondPosition = firstPosition + 1;
			}
			if(firstPosition >= (listPerm.size() - 1)){
				break;
			}
			tmpforSwap = listPerm.get(firstPosition);
			listPerm.set(firstPosition, listPerm.get(secondPosition));
			listPerm.set(secondPosition, tmpforSwap);
			++secondPosition;
			tmpList.add(new Permutation(listPerm));
		}
		
		if(tmpList.size() <= number){
			// Return all computed permutations
			return tmpList;
		} else {
			// Return 'number' permutations selected randomly
			List<Permutation> returnList = new ArrayList<Permutation>();
			Random rand = new Random();
			while(returnList.size() < number) {
				Integer randPosition = (Integer)rand.nextInt(tmpList.size());
				returnList.add(tmpList.get(randPosition));
				tmpList.remove(randPosition);
			}
			return returnList;
		}*/
		Random rnd = new Random();
		for(int i = 0; i < number; i++){
			int firstPos = rnd.nextInt(data.size());
			int secondPos = rnd.nextInt(data.size());
			
			List<Integer> listPerm = new LinkedList<Integer>(data);
			int firstValue = data.get(firstPos);
			listPerm.set(firstPos, data.get(secondPos));
			listPerm.set(secondPos, firstValue);
			
			tmpList.add(new Permutation(listPerm));
		}
		
		return tmpList;
	}
	
	/**
	 * Berechnet alle Nachbarn, die durch einfaches Verschieben
	 * gebildet werden k�nnen und gibt eine zuf�llige Auswahl davon
	 * zur�ck.
	 * @param number Anzahl der zur�ckgegebenen Permutaionen. Wenn
	 *   number aber gr��er als die Maximale Anzahl an Permutationen
	 *   ist [(n*(n+1))/2] wird nur die maximale Anzahl zur�ckgegeben. 
	 * @return
	 */
	public List<Permutation> getNeighborsByShift(int number){
		List<Permutation> tmpList = new LinkedList<Permutation>();
		Random rnd = new Random();
		for(int i = 0; i < number; i++){
			int sourcePos = rnd.nextInt(data.size());
			int targetPos = rnd.nextInt(data.size());
			
			List<Integer> listPerm = new LinkedList<Integer>(data);
			int value = data.get(sourcePos);
			listPerm.remove(sourcePos);
			listPerm.add(targetPos, value);
			
			tmpList.add(new Permutation(listPerm));
		}
		
		return tmpList;
	}
	
	public static Permutation switchDedicatedPos(int pos, Permutation per) {
		Permutation perm = new Permutation(per.data);
		perm.sortRandomly();
		for (int i = 1;i<=pos;i++) {
			int old = perm.data.indexOf(per.data.get(i));
			int value = per.data.get(i);
			perm.data.remove(old);
			perm.data.add(i, value);
		}
		return perm;
	}
	
	public Permutation crossover(Permutation secondPerm){
		List<Integer> newList = new ArrayList<Integer>();
		int sizeOfData = data.size();
		
		// Fill new list with Values of this permutation
		for (int i = 0; i < sizeOfData; i++) {
			if(i%2 == 0){
				newList.add(data.get(i));
			} else {
				newList.add(sizeOfData);
			}
		}
		
		int posInSecondPerm = 0;
		for (int i = 0; i < sizeOfData; i++) {
			if(newList.get(i) == sizeOfData){
				while(newList.contains(secondPerm.get(posInSecondPerm))){
					++posInSecondPerm;
				}
				newList.set(i, secondPerm.get(posInSecondPerm));
			}
		}
		return new Permutation(newList);
	}
	//TODO: swap, mutate, combine
}
